package com.briup.day08;

import java.util.Arrays;

/**
 * @author ThinkBook
 */
public class Test02_BinarySearch {
    //在有序序列 arr 中，查找 value对应的索引
    //如果找到返回其index下标值，找不到则返回 -(insertIndex + 1);
    public static int binarySearch(int[] arr, int value) {
        //定义变量，low high 用来标识搜索的 范围
        int low = 0;
        int high = arr.length - 1;
        int mid;

        while(true) {
            mid = (low + high) / 2;

            //比较value和mid位置值
            if(arr[mid] == value) {
                return mid;
            }else if(arr[mid] > value) {
                // 搜索范围 在mid的左侧
                high = mid - 1;
            }else {
                // 搜索范围 在mid的右侧
                low = mid + 1;
            }

            //判断查询是否结束
            if(high < low) {
                return -1*(low + 1);
            }
        }
    }

    //二分查找测试
    public static void main(String[] args) {
        int[] array = {5,7,2,3,8,1};
        //先排序，一定要保证 参加二分查找的序列 是有序的！
        Arrays.sort(array);
        System.out.println(Arrays.toString(array));

        int index = binarySearch(array,7);
        System.out.println("7的索引: " + index);

        index = binarySearch(array,3);
        System.out.println("3的索引: " + index);

        index = binarySearch(array,4);
        System.out.println("4的索引: " + index);

        index = Arrays.binarySearch(array,4);
        System.out.println("Arrays工具类方法，4的索引: " + index);
    }
}
